//
//  Problem2099.swift
//  LeetCode
//
//  Created by 武侠 on 2023/6/29.
//  Copyright © 2023 zhulongiMac02. All rights reserved.
//

import UIKit

/*
 2099. 找到和最大的长度为 K 的子序列 简单
 
 给你一个整数数组 nums 和一个整数 k 。你需要找到 nums 中长度为 k 的 子序列 ，且这个子序列的 和最大 。
 请你返回 任意 一个长度为 k 的整数子序列。
 子序列 定义为从一个数组里删除一些元素后，不改变剩下元素的顺序得到的数组。
 示例 1：
     输入：nums = [2,1,3,3], k = 2
     输出：[3,3]
     解释：
     子序列有最大和：3 + 3 = 6 。
 示例 2：
     输入：nums = [-1,-2,3,4], k = 3
     输出：[-1,3,4]
     解释：
     子序列有最大和：-1 + 3 + 4 = 6 。
 示例 3：
     输入：nums = [3,4,3,3], k = 2
     输出：[3,4]
     解释：
     子序列有最大和：3 + 4 = 7 。
     另一个可行的子序列为 [4, 3] 。
 提示：

 1 <= nums.length <= 1000
 -105 <= nums[i] <= 105
 1 <= k <= nums.length
 */
class Problem2099: NSObject {
    /*
     思路：
     1: 定义一个长度为k的数组list，里面按照降序存储是nums中最大的k个值的索引位置，
        例如：[-1,-2,3,4], k = 3；list = [4, 3, -1]
     2: list进行sort，然后转换成nums中的值
     */
    func maxSubsequence(_ nums: [Int], _ k: Int) -> [Int] {
        var index = Array(repeating: -1, count: k)
        index[0] = 0
        var last = 0        // 记录index里面已经存储了值的最后一个位置
        
        for i in 1..<nums.count {
            // 当前值和index里面最后一个值比较大小
            if nums[i] <= nums[index[last]] {
                // 如果index后面有未填入数据的位置，那么把i放到里面：例如  1 2 -1 -1， 把i放到-1的位置
                if last < nums.count, last != index.count-1 {
                    last += 1
                    index[last] = i
                }
                continue
            } else if last < nums.count, last != index.count-1 {
                // nums[i] 比最小的值大，而且index中还有空位置，那么last移动到空位置上
                last += 1
            }
            
            // 因为last是index中非空位置的最后一个有值的位置，而且nums[i]比他大，那么i更新到last中
            index[last] = i
            // 然后看看前面的位置是否也比i大
            for i in (0..<last).reversed() {
                if nums[index[i+1]] > nums[index[i]] {
                    index.swapAt(i+1, i)
                }
            }
        }
        return index.sorted().map { i in
            nums[i]
        }
    }
}
